深入理解KMP算法及其应用

本文将详细介绍KMP算法的核心概念和实现步骤，帮助读者更好地理解和应用这一高效字符串匹配算法。

总结不易，如果对你有帮助，请点赞关注支持一下。
微信搜索程序dunk，关注公众号，获取博主的数据结构与算法的代码笔记。

目录

• KMP算法概述


• KMP算法详解
  
  
  
  • BF(Brute Force)算法
  
  
  • KMP算法
  
  
  • 计算next数组
  
  
  • next数组的作用
  
  
  
  


• LeetCode题目解析：28. 实现 strStr()

KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，主要用于在一个较长的文本串（主串）中查找一个较短的模式串（子串）的首次出现位置。

KMP算法详解

KMP算法的核心在于通过预处理模式串来构建一个next数组，该数组记录了模式串中每个位置的最长公共前后缀长度。这样在匹配过程中，当发生失配时，可以通过next数组快速跳过已经匹配的部分，从而提高匹配效率。

BF(Brute Force)算法

BF算法是最简单的字符串匹配算法，通过逐个字符比较的方式进行匹配。其时间复杂度为O(m*n)，其中m是主串的长度，n是模式串的长度。

class Solution {
    public int strStr(String haystack, String needle) {
        int len1 = haystack.length();
        int len2 = needle.length();
        if (len2 == 0) return 0;
        int l = 0;
        int r = 0;
        while (l             if (haystack.charAt(l) == needle.charAt(r)) {
                l++;
                r++;
            } else {
                l = l - r + 1;
                r = 0;
            }
        }
        if (r == len2) {
            return l - r;
        }
        return -1;
    }
}

KMP算法

KMP算法通过构建next数组来优化匹配过程。具体步骤如下：

计算next数组

next数组用于记录模式串中每个位置的最长公共前后缀长度。通过遍历模式串并更新next数组，可以在失配时快速跳转到下一个可能的匹配位置。

private static int[] getNext(String target) {
    int[] next = new int[target.length()];
    int len = -1;
    int y = 0;
    next[0] = -1;
    while (y         if (len == -1 || target.charAt(len) == target.charAt(y)) {
            len++;
            y++;
            next[y] = len;
        } else {
            len = next[len];
        }
    }
    return next;
}

next数组的作用

在匹配过程中，当发生失配时，通过next数组可以快速找到下一个可能的匹配位置，从而避免重复比较已经匹配过的部分，提高匹配效率。

LeetCode题目解析：28. 实现 strStr()

题目要求实现一个函数`strStr()`，在主串`haystack`中查找模式串`needle`首次出现的位置。如果模式串为空，则返回0；如果模式串不在主串中，则返回-1。

示例 1：
输入: haystack = "hello", needle = "ll"
输出: 2

示例 2：
输入: haystack = "aaaaa", needle = "bba"
输出: -1

class Solution {
    public int strStr(String haystack, String needle) {
        if (needle.length() == 0) return 0;
        return kmpSearch(haystack, needle);
    }

    public int kmpSearch(String haystack, String needle) {
        int[] next = getNext(needle);
        int x = 0;
        int y = 0;
        while (x             if (y == -1 || haystack.charAt(x) == needle.charAt(y)) {
                x++;
                y++;
            } else {
                y = next[y];
            }
        }
        if (y == needle.length()) {
            return x - y;
        }
        return -1;
    }

    public int[] getNext(String needle) {
        int[] next = new int[needle.length()];
        int len = -1;
        int y = 0;
        next[0] = -1;
        while (y             if (len == -1 || needle.charAt(len) == needle.charAt(y)) {
                len++;
                y++;
                next[y] = len;
            } else {
                len = next[len];
            }
        }
        return next;
    }
}